package lcr;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Test0094 {
    public static void main(String[] args) {
        new Solution0094_1().minCut("aab");
    }
}

class Solution0094_1 {
    public int minCut(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;

        boolean records[][] = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            Arrays.fill(records[i], true);
        }

        for (int i = 0; i < length; i++) {
            for (int j = i-1; j >= 0; j--) {
                records[j][i] = chars[j] == chars[i] && records[j+1][i-1];
            }
        }

        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = i;
            for (int j = 0; j <= i; j++) {
                if (records[j][i]){
                    if (j==0){
                        dp[i] = 0;
                        break;
                    }

                    dp[i] = Math.min(dp[i], dp[j-1]+1);
                }
            }
        }
        return dp[length-1];
    }
}
